C++ স্ট্যান্ডার্ড লাইব্রেরিতে Searching এবং Sorting এর জন্য বেশ কিছু গুরুত্বপূর্ণ অ্যালগরিদম সরবরাহ করা হয়। এর মধ্যে প্রধান তিনটি হল std::sort(), std::find(), এবং std::binary_search()। এগুলো ডেটা সংগ্রহের সন্নিবেশ, অনুসন্ধান এবং সাজানোর জন্য ব্যবহৃত হয়।
এখানে এই তিনটি অ্যালগরিদমের কাজ এবং ব্যবহার সম্পর্কে বিস্তারিত আলোচনা করা হলো:
১. std::sort() – Sorting Algorithm
std::sort() একটি Sorting Algorithm, যা C++ স্ট্যান্ডার্ড লাইব্রেরির <algorithm> হেডার ফাইলে থাকে। এটি কনটেইনারের উপাদানগুলো সাজানোর জন্য ব্যবহৃত হয়। std::sort() সাধারণত Quick Sort অথবা Heap Sort অ্যালগরিদম ব্যবহার করে এবং এর O(n log n) টাইম কমপ্লেক্সিটি রয়েছে।
Syntax:
std::sort(iterator begin, iterator end);begin: কনটেইনারের প্রথম উপাদান।end: কনটেইনারের শেষ উপাদান (এটি সাজানোর জন্য সহায়ক হয়)।
উদাহরণ (std::sort):
#include <iostream>
#include <vector>
#include <algorithm> // std::sort
int main() {
std::vector<int> vec = {5, 2, 8, 1, 3};
// std::sort() ব্যবহার করে ভেক্টর সাজানো
std::sort(vec.begin(), vec.end());
// সাজানো উপাদান প্রিন্ট করা
for (int num : vec) {
std::cout << num << " ";
}
return 0;
}আউটপুট:
1 2 3 5 8এখানে, std::sort() ভেক্টর vec এর উপাদানগুলো সাজিয়ে দিয়েছে।
কাস্টম কম্প্যারিজন ফাংশন:
আপনি যদি নিজস্ব ক্রম অনুসারে সাজাতে চান, তবে একটি কাস্টম কম্প্যারিজন ফাংশন ব্যবহার করতে পারেন। উদাহরণস্বরূপ:
#include <iostream>
#include <vector>
#include <algorithm>
bool compare(int a, int b) {
return a > b; // Descending order
}
int main() {
std::vector<int> vec = {5, 2, 8, 1, 3};
std::sort(vec.begin(), vec.end(), compare);
for (int num : vec) {
std::cout << num << " ";
}
return 0;
}আউটপুট:
8 5 3 2 1২. std::find() – Searching Algorithm
std::find() একটি Searching Algorithm, যা একটি সিকোয়েন্সে একটি নির্দিষ্ট উপাদান খুঁজে বের করার জন্য ব্যবহৃত হয়। এটি linear search ব্যবহার করে, অর্থাৎ এটি একটি উপাদান খুঁজতে কনটেইনারের প্রতিটি উপাদান পরীক্ষা করে। এটি O(n) টাইম কমপ্লেক্সিটি ধারণ করে।
Syntax:
std::find(iterator begin, iterator end, const T& value);begin: অনুসন্ধান শুরুর পয়েন্ট।end: অনুসন্ধানের শেষ পয়েন্ট।value: যে মানটি খুঁজতে চান।
উদাহরণ (std::find):
#include <iostream>
#include <vector>
#include <algorithm> // std::find
int main() {
std::vector<int> vec = {10, 20, 30, 40, 50};
// std::find() ব্যবহার করে একটি উপাদান খোঁজা
auto it = std::find(vec.begin(), vec.end(), 30);
if (it != vec.end()) {
std::cout << "Found: " << *it << std::endl;
} else {
std::cout << "Not Found" << std::endl;
}
return 0;
}আউটপুট:
Found: 30এখানে, std::find() 30 মানটি ভেক্টরের মধ্যে খুঁজে পেয়েছে এবং এটি প্রিন্ট করেছে।
৩. std::binary_search() – Searching Algorithm
std::binary_search() একটি Searching Algorithm যা binary search পদ্ধতি ব্যবহার করে একটি সাজানো কনটেইনারে দ্রুত অনুসন্ধান করে। এটি কেবল তখনই কার্যকরী, যখন কনটেইনারটি সাজানো থাকে। এর O(log n) টাইম কমপ্লেক্সিটি থাকে, যা std::find() থেকে অনেক দ্রুত।
Syntax:
bool std::binary_search(iterator begin, iterator end, const T& value);begin: অনুসন্ধান শুরুর পয়েন্ট।end: অনুসন্ধানের শেষ পয়েন্ট।value: যে মানটি খুঁজতে চান।
উদাহরণ (std::binary_search):
#include <iostream>
#include <vector>
#include <algorithm> // std::binary_search
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
// std::binary_search() ব্যবহার করে একটি উপাদান খোঁজা
bool found = std::binary_search(vec.begin(), vec.end(), 5);
if (found) {
std::cout << "Found!" << std::endl;
} else {
std::cout << "Not Found!" << std::endl;
}
return 0;
}আউটপুট:
Found!এখানে, std::binary_search() 5 মানটি সাজানো ভেক্টরের মধ্যে খুঁজে পেয়েছে।
গুরুত্বপূর্ণ নোট:
std::binary_search()শুধুমাত্র সাজানো কনটেইনারের জন্য কাজ করে। যদি কনটেইনারটি সাজানো না থাকে, তবে এটি সঠিক ফলাফল প্রদান করবে না।- যদি
std::binary_search()ব্যবহার করার পর আপনি সেই মানের অবস্থান জানতে চান, তাহলেstd::lower_bound()বাstd::upper_bound()ব্যবহার করতে পারেন।
পার্থক্য সারণী
| Algorithm | Type | Time Complexity | Requires Sorted Data |
|---|---|---|---|
std::sort() | Sorting | O(n log n) | No |
std::find() | Searching | O(n) | No |
std::binary_search() | Searching | O(log n) | Yes |
উপসংহার
std::sort(): এটি একটি কনটেইনারের উপাদানগুলোকে সাজানোর জন্য ব্যবহৃত হয় এবং এটি O(n log n) টাইম কমপ্লেক্সিটিতে কাজ করে।std::find(): এটি একটি সিকোয়েন্সের মধ্যে একটি উপাদান খুঁজে বের করার জন্য ব্যবহৃত হয় এবং এটি linear search পদ্ধতি ব্যবহার করে, যার O(n) টাইম কমপ্লেক্সিটি থাকে।std::binary_search(): এটি একটি সাজানো কনটেইনারে একটি উপাদান খুঁজে বের করার জন্য binary search পদ্ধতি ব্যবহার করে, যার O(log n) টাইম কমপ্লেক্সিটি থাকে।
এই অ্যালগরিদমগুলো C++ প্রোগ্রামে ডেটা অনুসন্ধান এবং সাজানোর জন্য গুরুত্বপূর্ণ টুল হিসেবে কাজ করে, এবং সঠিক ব্যবহারের মাধ্যমে কোডের কর্মদক্ষতা উন্নত করা সম্ভব।
Read more
